package com.michael.demos.base.java.queue;

import java.util.*;

/**
 * 类功能描述:
 * <pre>
 *   查询 TOP K 示例
 * </pre>
 *
 * @author Michael
 * @version 1.0
 * @date 2020/9/15 10:24
 */
public class TopK {

    /** 使用最小堆 */
    private final PriorityQueue<Integer> queue;
    private final Integer maxSize;

    public TopK(Integer maxSize) {
        this.maxSize = maxSize;
        this.queue = new PriorityQueue<>(maxSize);
    }

    public void add(Integer value) {
        int size = queue.size();
        if (maxSize > size) {
            queue.add(value);
        } else {
            Integer root = queue.peek();
            // 当前元素比最小值大，删除最小值，增加新值
            if (root < value) {
                queue.remove();
                queue.add(value);
            }
        }
    }

    /** 获取最终排序结果值 */
    public List<Integer> getResult() {
        List<Integer> result = new ArrayList<>(maxSize);

        while (!queue.isEmpty()) {
            result.add(queue.remove());
        }

        Collections.reverse(result);

        return result;
    }

    public static void main(String[] args) {

        System.out.println("开始 -> " + System.currentTimeMillis());
        TopK topK = new TopK(10);

        Integer dataCount = 100000000;
        Random random = new Random();
        for (int i = 0; i < dataCount; i++) {
            topK.add(random.nextInt(dataCount));
        }

        List<Integer> result = topK.getResult();
        System.out.println("结束 -> " + System.currentTimeMillis());
        result.forEach(System.out::println);
    }

}
